package org.example;

public class Test1 {
    //leetcode 74 搜索二维矩阵
    //https://leetcode.cn/problems/search-a-2d-matrix/description/
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        if (target < matrix[0][0] || target > matrix[m-1][n-1]) return false;
        for (int i = 0; i < m; i++) {
            if (target == matrix[i][n-1]) return true;
            else if (target > matrix[i][n-1]) continue;
            else {
                //在当前行查找target
                if (target < matrix[i][0]) return false;
                //二分查找
                int left = 0, right = n-1;
                while (left < right) {
                    int mid = left + (right-left) / 2;
                    if (matrix[i][mid] < target) left = mid + 1;
                    else right = mid;
                }
                return matrix[i][left] == target;
            }
        }
        return false;
    }
}
